CS157b Spring 2018Practice Final

To study for the final I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice final is below. Here are some facts about the actual final: (a) It is comprehensive (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) It is 10 problems (3pts each), 6 problems will be on materials since the midterm, 4 problems will be from the topics of the midterm. (f) Two problems will be exactly (less typos) off of the practice final, and one will be off of the practice midterm.

1. What is undo logging? Give the two rules a transaction manager uses when undo logging of transaction is being done.
2. Consider the sequence of operations and log records:
   `langle START\ T_1 rangle`, `I_1(A)`, `R_1(A,t_1)`, `t_1:=t_1*2`, `langle START\ T_2 rangle`,
   `langle T_1, A, 4 rangle`, `W_1(A,t_1)`, `langle START\ T_3 rangle`, `I_2(B)`, `R_2(B,t_2)`, `t_2:= t_2*2`,
   `langle T_2, B, 12 rangle`, `W_2(B,t)`, `langle T_3, C, 1 rangle`, `W_3(C,5)`, `O_1(A)`, `langle COMMIT\ T_1 rangle`, `O_2(B)`, `langle COMMIT\ T_2 rangle`.
   Suppose we started a non-quiescent checkpoint right after the `langle T_1, A, 4 rangle`, what transactions would be listed in the start checkpoint? When would be the earliest that an end checkpoint could be written?
3. Define the following terms: (a) serial schedule, (b) serializable schedule, (c) conflict serializable schedule. Give an example of a serializable schedule which is not conflict serializable.
4. Give an argument based on two transactions (you don't have to show the general `n` transaction case) that two phase locking guarantees conflict serializability.
5. Briefly explain how timestamp scheduling and multi-version timestamp scheduling work (Should be convincing to someone who didn't know the concepts). Give an example schedule for each where a transaction would abort.
6. Define the following types of schedules: (a) recoverable, (b) avoids cascading rollbacks, and (c) strict 2PL. Give an example of a serializable schedule which is not recoverable.
7. Give the parallel algorithm from class for computing the join of two relations $R \bowtie S$. Give its cost on `N` machines. Give the distributed algorithm from class for computing $R \bowtie S$ on two machines.
8. Define the following distributed locking concepts: (a) centralized locking, (b) Lock Coordinator, (c) primary copy locking. Suggest an algorithm to avoid deadlocks in the distributed setting.
9. Give an example different from class of a schema a mediator might expose to application queries and queries to that schema might be re-written to two distinct data sources.
10. Define the following OLAP concepts (a) star-schema, (b) slicing data, (d) cube. How would the roll up operation in SQL help in computing frequent item sets?